// 2025/4/3
// https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
// 颜色分类

class Solution {
    public:
        void sortColors(vector<int>& nums) {
            int n = nums.size();
            int red = 0, white = 0, blue = n - 1;
            while(white < n)
            {
                while(red < n && nums[red] == 0) red++;
                if(white <= red) white = red + 1;
                while(white < n && nums[white] != 0) white++;
                if(white < n) swap(nums[red], nums[white]);
            }
    
            while(white >= 0)
            {
                while(blue >= 0 && nums[blue] == 2) blue--;
                if(white >= blue) white = blue - 1;
                while(white >= 0 && nums[white] != 2) white--;
                if(white >= 0) swap(nums[blue], nums[white]);
            }
        }
    };